\documentclass[10.5pt,compsoc,UTF8]{CjC}
\usepackage{CTEX}
\usepackage{graphicx}
\usepackage{footmisc}
\usepackage{subfigure}
\usepackage{url}
\usepackage{multirow}
\usepackage{multicol}
\usepackage[noadjust]{cite}
\usepackage{amsmath,amsthm}
\usepackage{amssymb,amsfonts}
\usepackage{booktabs}
\usepackage{color}
\usepackage{ccaption}
\usepackage{booktabs}
\usepackage{float}
\usepackage{fontspec}
\setmainfont{Times New Roman}
\usepackage{algorithm2e}
\SetAlgoSkip{smallskip}
\usepackage{fancyhdr}
\usepackage{caption}
\usepackage{xcolor,stfloats}
\usepackage{comment}
\setcounter{page}{1}
\graphicspath{{figures/}}
\usepackage{cuted}
\usepackage{captionhack}
\usepackage{epstopdf}
\usepackage{gbt7714}
\usepackage{stfloats}
\usepackage{amsmath}
\usepackage{arydshln}
\usepackage{svg}
\usepackage{adjustbox}
\usepackage{ragged2e} % 在导言区添加
\newcommand{\cys}{\textcolor{red}}
%===============================%

%=======设置奇偶页页眉=======%
\headevenname{\mbox{\quad} \hfill  \mbox{\zihao{-5}{计\quad \quad 算\quad \quad 机\quad \quad 学\quad \quad 报} \hspace {50mm} \mbox{2023 年}}}%
\headoddname{1 期 \hfill
QT框架下算法驱动的迷宫探险游戏开发}
%=======设置奇偶页页眉=======%

\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\setcounter{footnote}{0}
\renewcommand\footnotelayout{\zihao{5-}}
\newtheoremstyle{mystyle}{0pt}{0pt}{\normalfont}{1em}{\bf}{}{1em}{}
\theoremstyle{mystyle}
\renewcommand\figurename{figure~}
\renewcommand{\thesubfigure}{(\alph{subfigure})}
\newcommand{\upcite}[1]{\textsuperscript{\cite{#1}}}
\renewcommand{\labelenumi}{(\arabic{enumi})}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}
\newcommand{\abc}{\color{white}\vrule width 2pt}
\renewcommand{\bibsection}{}
\makeatletter
\renewcommand{\@biblabel}[1]{[#1]\hfill}
\SetKwComment{Comment}{/* }{ */}
\makeatother
\setlength\parindent{2em}

\pagestyle{CjCheadings}
% \setmainfont{Times New Roman}

%===========================================================%
\begin{document}

\hyphenpenalty=50000
\makeatletter
\newcommand\mysmall{\@setfontsize\mysmall{7}{9.5}}
\newenvironment{tablehere}
  {\def\@captype{table}}

\let\temp\footnote
\renewcommand \footnote[1]{\temp{\zihao{-5}#1}}

%=======设置首页页眉=======%
\thispagestyle{empty}%
\begin{table*}[!t]
\vspace {-13mm}
\onecolumn
\noindent\begin{tabular}{p{168mm}}
\zihao{5-}
第1卷\quad 第1期 \hfill 计\quad 算\quad 机\quad 学\quad 报\hfill Vol. 114  No. 1\\
\zihao{5-}
2025年7月 \hfill CHINESE JOURNAL OF COMPUTERS \hfill Jul. 2025\\
\hline\\[-5.5mm]
\hline\end{tabular}\end{table*}
%=======设置首页页眉=======%

%中文标题、作者与注脚
{
\centering
\vspace {11mm}
{\zihao{2} \heiti QT框架下算法驱动的迷宫探险游戏开发 }

\vskip 5mm

\begin{center}
{\zihao{3}\fangsong 王稳淞$^{1)}$ \quad  程宇山$^{2)}$ \quad 徐伟杰$^{3)}$ \quad 林书豪$^{4)}$}
\end{center}

\vspace {1mm}

\zihao{6}{$^{1)}$(东北大学 计算机科学与技术, 计算机2305 20235870)}

\zihao{6}{$^{2)}$(东北大学 计算机科学与技术, 计算机2304 20236719)}

\zihao{6}{$^{3)}$(东北大学 计算机科学与技术, 计算机2304 20234997)}

\zihao{6}{$^{4)}$(东北大学 计算机科学与技术, 计算机2304 20237440)}

% \zihao{6}{\textsf{论文定稿后，作者署名、单位无特殊情况不能变更。若变更，须提交签章申请，国家为中国可以不写，省会城市不写省名，其他国家必须写国家名。}}
}%中文标题、作者与注脚

\vskip 5mm

\zihao{5-}{
\setlength{\baselineskip}{16pt}\selectfont{
\noindent {\heiti 摘\quad 要\quad }
本文设计并实现了一个基于多种算法的迷宫探险游戏系统。系统采用Qt框架构建，融合了分治递归迷宫生成算法、动态规划路径优化最大收益算法、贪心资源收集算法以及回溯搜索算法、分支限界算法，解决了迷宫
生成、资源分配、路径规划、解谜与战斗等关键问题，从而提升算法设计能力和工程实践能力。
在迷宫生成方面，采用分治递归算法生成具有连通性的复杂迷宫结构，通过随机种子与特判语句控制并确保生成结果的多样性；
在路径规划方面，设计了基于三维状态压缩dp的最优收益路径算法，能够在尽可能避开陷阱的同时最大化收益，并利用位掩码保存路径信息，最大压缩空间；
在资源收集方面，实现了贪心算法配合bfs算法，提高了资源收集效率。
在BOSS战斗方面，设计了基于分支限界的战斗策略优化算法，集成了多种技能模块并设计精美战斗场景动画，能够在有限资源下最大化击败BOSS的概率。
在回溯解密方面，采用回溯算法，枚举所有可行解，得到正确结果。
通过对比实验验证了各算法在不同规模迷宫中的性能表现，实验结果表明该系统在15×15规模的迷宫中，动态规划算法相比传统深度优先搜索算法在时间消耗方面提升了60.7\%，相比未进行状态压缩的算法，存储空间消耗方面减少了50\%，贪心算法在资源收集效率上比随机搜索提高了42.3\%。
所有代码和数据集将在以下网址公开：https://gitee.com/cys710/alg-design}
}
\vspace {5mm}

\zihao{5-}{\noindent
{\heiti 关键词 \quad }{分治，动态规划，贪心，回溯，分支限界，QT  }
}\par\noindent
\zihao{5-}{\heiti 中图法分类号\quad } TP\rm{514 \quad     }


\vskip 5mm

\begin{center}
\zihao{3}{\heiti Algorithm-driven maze exploration game development under QT} \\
\vspace{5mm}
\zihao{5}{WANG Wen-Song$^{1)}$ \quad CHENG Yu-Shan$^{2)}$ \quad XU Wei-Jie$^{3)}$ \quad LIN Shu-Hao$^{4)}$}\\
\vspace{1mm}
\zihao{6}{$^{1)}$(School of Computer Science and Engineering, Northeastern University, Computer Science Class 2305, Student ID 20235870)}

\zihao{6}{$^{2)}$(School of Computer Science and Engineering, Northeastern University, Computer Science Class 2304, Student ID 20236719)}

\zihao{6}{$^{3)}$(School of Computer Science and Engineering, Northeastern University, Computer Science Class 2304, Student ID 20234997)}

\zihao{6}{$^{4)}$(School of Computer Science and Engineering, Northeastern University, Computer Science Class 2304, Student ID 20237440)}

\end{center}

\zihao{5}{
{\noindent\bf Abstract}\quad
\zihao{5}{\noindent This paper designs and implements a maze exploration game system based on multiple algorithms. The system is built with the Qt framework, integrating the divide-and-conquer recursive maze generation algorithm, the dynamic programming path optimization maximum benefit algorithm, the greedy resource collection algorithm, the backtracking search algorithm, and the branch-and-bound algorithm, solving key problems such as maze
generation, resource allocation, path planning, puzzle solving and combat, thereby improving algorithm design capabilities and engineering practice capabilities.
In terms of maze generation, a divide-and-conquer recursive algorithm is used to generate a complex maze structure with connectivity, and the random seed and special judgment statements are used to control and ensure the diversity of the generated results;
In terms of path planning, an optimal benefit path algorithm based on three-dimensional state compression dp is designed, which can maximize the benefits while avoiding traps as much as possible, and use bit masks to save path information and compress space to the maximum;
In terms of resource collection, a greedy algorithm is implemented in conjunction with the bfs algorithm to improve resource collection efficiency.
In terms of BOSS combat, a combat strategy optimization algorithm based on branch-and-bound is designed, which integrates multiple skill modules and designs exquisite combat scene animations, which can maximize the probability of defeating BOSS under limited resources.
In terms of backtracking decryption, a backtracking algorithm is used to enumerate all feasible solutions and obtain the correct result.
The performance of each algorithm in mazes of different sizes is verified through comparative experiments. The experimental results show that in a maze of 15×15 scale, the dynamic programming algorithm improves the time consumption by 60.7% compared with the traditional depth-first search algorithm, and reduces the storage space consumption by 50% compared with the algorithm without state compression. The greedy algorithm improves the resource collection efficiency by 42.3% compared with random search.
All codes and data sets will be made public at the following website: https://gitee.com/cys710/alg-design
\par}}

\vspace {5mm}

% \zihao{5}{
% {\noindent\bf Keywords}\quad 中文关键字与英文关键字对应且一致，\textbf{不要用英文缩写};
% key word; key word; key word* *字体为5号Times new Roman * Key words
% \par}

\zihao{5}{
{\noindent\bf Keywords}\quad
divide and conquer, dynamic programming, greedy algorithm, backtracking, branch and bound, Qt framework
\par}

\zihao{5}
\vskip 1mm
\begin{multicols}{1}

\section{\heiti 引言}

% 这是一个CTEX的utf-8编码例子，{\kaishu 这里是楷体显示}，{\songti 这里是宋体显示}，{\heiti 这里是黑体显示}，{\fangsong 这里是仿宋显示}。另外一种方式：\textit{这是楷体显示，but英文和数字是斜体abcABC123}，\textsf{这是黑体显示abcACB123}，\texttt{这是仿宋显示abcABC123}。

迷宫探险游戏作为经典的益智游戏类型，不仅具有娱乐价值，更是算法设计与数据结构应用的理想载体。随着计算机技术的快速发展，游戏开发已成为验证和展示算法效果的重要平台。传统的迷宫游戏多采用简单的随机生成算法和基础的路径搜索策略，缺乏复杂的优化机制和多目标决策能力，难以充分体现算法设计的精妙之处。

近年来，算法可视化教学和实践项目备受关注。通过游戏化的方式展示算法原理，不仅能够提高学习者的兴趣，还能够加深对算法本质的理解。迷宫问题作为图论和搜索算法的经典应用场景，涉及路径规划、资源分配、策略优化等多个核心问题，为多种算法的融合应用提供了良好的实验平台。

本文设计并实现了一个基于多算法融合的迷宫探险游戏系统，旨在通过实际项目开发提升算法设计能力和工程实践水平。该系统采用Qt框架构建，集成了分治递归、动态规划、贪心算法、回溯搜索和分支限界等多种经典算法，系统性地解决了迷宫生成、路径规划、资源收集、战斗策略优化等关键技术问题。

与现有迷宫游戏相比，本系统的主要特点包括：
(1)采用分治递归算法生成具有良好连通性和结构复杂度的迷宫，通过随机种子与特判控制确保生成结果的多样性；
(2)设计基于三维状态压缩的动态规划算法，在避开陷阱的同时实现最优收益路径规划，并通过位掩码技术有效压缩存储空间；
(3)实现贪心算法与广度优先搜索的混合策略，显著提高资源收集效率；
(4)构建基于分支限界的BOSS战斗策略优化系统，在有限资源约束下最大化战斗胜率；
(5)采用回溯算法进行解密，枚举所有可行解，得到正确结果。

\section {\heiti 课设任务及要求}

\subsection{\heiti 设计目标}

1. 开发一款由经典算法设计策略全栈驱动的迷宫探险游戏，AI玩家
（算法控制）需从起点出发，穿越随机生成的迷宫，收集资源、
避开陷阱、破解机关，击败守卫BOSS，最终抵达终点。

2. 能够通过分治、动态规划、贪心、回溯、分支限界算法解决迷宫
生成、资源分配、路径规划、解谜与战斗等关键问题，从而提升
算法设计能力和工程实践能力。
\subsection{\heiti 任务分解}

(1) \textbf{迷宫生成模块}：使用分治法生成迷宫，无孤立区域，存在唯一通路。

{\kaishu 需求：1）迷宫无孤立区域且存在唯一通路。（2）支持多种尺寸。
最小尺寸为7×7，只能容纳较少机关/资源/陷阱。理想尺寸为
15×15，可设置较多机关/资源/陷阱，增加策略性。（3）起点、终
点、资源、陷阱、机关、BOSS均随机分布。（4）可选：可视化生成
过程（动画）。}

(2) \textbf{路径规划模块}：设采用动态规划进行资源收集路径规划（作为实时策略的金标准）

{\kaishu 任务：计算从起点到终点的最优资源收集路径，避开陷阱，优先拾取
资源。}

{\kaishu 需求：路径可视化（可选）。}

(3) \textbf{资源管理模块}：采用贪心算法设计实时资源拾取策略。

{\kaishu 任务：玩家视野受限于周围区域，每次移动时优先选择视野内
"性价比"（例如单位距离收益最大）最高的资源，重复直至无资源可
拾取。}

(4) \textbf{战斗系统模块}：采用分支限界设计BOSS战策略优化

{\kaishu 任务：在限定回合内击败BOSS，寻找最小代价的技能序列。}

(5) \textbf{解谜模块}：采用回溯法解谜关卡，确保能够找到所有可行解。

{\kaishu 输入：一个3位密码锁的位置和线索（如每位密码为素数且不重复、
或第1位是偶数等）。}

{\kaishu 输出：密码}

\section{\heiti 主要成果论述}

\subsection{\heiti 迷宫生成}

\subsubsection{\heiti 问题定义}
在一个n×n的二维网格中，生成一个迷宫，使得每个单元格都可以通过唯一的路径从起点到达终点，并且没有孤立区域。

\subsubsection{\heiti 算法设计}
采用分治递归算法，将迷宫划分为四个子区域，递归地生成每个子区域的迷宫。通过随机种子和特判语句控制生成结果的多样性，确保每次生成的迷宫都具有不同的结构。

迷宫划分： 在地图大小足够大的情况下，从迷宫的中轴线开始进行划分，划分为四个区域，在四个区域的划分墙上随机选择位置开四个开口，确保区域连通，随机选一个开口进行封闭，并在第一次划分时，在封闭的开口两侧确定起始点和终止点。
不断递归；当地图的大小小于等于4*4时，进行环和独立区域的判别并进行覆盖，生成唯一通路迷宫。

基问题判定处理：以下为不同处理规模的迷宫生成处理方式：

% 唯一通路证明：

% 在每次划分时，确保每个子区域都可以通过唯一的路径从起点到达终点。通过随机选择开口和封闭开口的方式，保证了迷宫的连通性和唯一性。
% 对于每个子区域，递归地应用相同的划分和开口选择策略，确保每个子区域都满足唯一通路的要求。
% 当划分到Adhoc级别时，考虑当前所处环境的大小和结构，填充地图，确保唯一通路。

\subsubsection{唯一通路与无孤立区域分析与证明}

分治递归迷宫生成算法每次将当前区域分割为四个子区域，并在分割线上随机开设"门"以连接子区域。每次递归都保证每个子区域通过至少一个门与其它区域连通，并随机关闭一个门，避免形成环路。

\textbf{唯一通路证明}：

设初始迷宫为全墙壁，递归分割时，每次只在分割线上开设一个门（其余为墙），并随机关闭一个门。这样，每个新生成的子区域仅通过一个门与外部连通，等价于在树结构中添加一条边，避免形成环路。%\cys{???}
整体迷宫结构等价于一棵生成树（spanning tree），树的性质保证了任意两点之间仅有唯一一条简单路径。因此，从起点到终点的路径唯一，且无多余环路。
\[
|E| = |V| - 1
\]
其中 $E$ 为通路集合，$V$ 为可通行单元格集合。

由于上述划分中我们在对于大小小于4*4的区域时，并未采取同样的划分操作，因此对于这些小区域，可能会出现环，导致其中的两个点之间存在多条不同的路径，所以我们对于大小小于等于4*4的区域，进行判别和单独的处理。我们会对其图形中的门的位置，进行判别，在特定的位置生成墙壁，以此来实现两点之间有唯一的路径，下列图片是一些简单的样式的处理效果图。

注：效果图仅仅是一种情况，并不代表是唯一的处理方式。其具体的处理方式与我们的图形中门的位置有关。

通过这样的方式，我们不仅实现了从起点到终点有唯一路径，而且实现了对于任意两点之间都仅有唯一的一条路径。

\begin{figure*}[!t]
  \begin{minipage}{0.31\textwidth}
    \centering
    \includegraphics[height = 2cm]{image/2-2-1.pdf} 
    \caption{2-2}
  \end{minipage}
    \begin{minipage}{0.31\textwidth}
    \centering
    \includegraphics[height = 2cm]{image/2-2-2.pdf}
    \caption{2-3}
  \end{minipage}
      \begin{minipage}{0.31\textwidth}
    \centering
    \includegraphics[height = 2cm]{image/2-2-3.pdf}
    \caption{3-2}
  \end{minipage}
\end{figure*}

\begin{figure*}[!t]
  \begin{minipage}{0.31\textwidth}
    \centering
    \includegraphics[height = 2cm]{image/2-2-4.pdf} 
    \caption{3-3}
  \end{minipage}
    \begin{minipage}{0.31\textwidth}
    \centering
    \includegraphics[height = 2cm]{image/2-2-5.pdf}
    \caption{3-4}
  \end{minipage}
      \begin{minipage}{0.31\textwidth}
    \centering
    \includegraphics[height = 2cm]{image/2-2-6.pdf}
    \caption{4-4}
  \end{minipage}
\end{figure*}
\textbf{无孤立区域证明}：

每次递归分割时，所有子区域都通过门与主区域连通，且不会出现完全被墙壁包围的孤立区域。递归终止时，所有可通行区域均可通过门与起点、终点连通。
\[
\forall C, \exists P = \{S, \ldots, C\} \subseteq G
\]
其中 $C$ 为任意可通行区域，$S$ 为起点或终点，$G$ 为迷宫连通图。

\subsubsection{时间与空间复杂度分析}

每次递归将区域分为四个子区域，递归深度为 $O(\log n)$，每层处理 $O(n^2)$ 个单元格\cite{wang2018jisuanji}。总体复杂度为：
\[
T(n) = 4T\left(\frac{n}{2}\right) + O(n^2) = O(n^2)
\]
{\kaishu 其中，} $T(n)$ {\kaishu 表示生成 $n \times n$ 迷宫所需的时间复杂度，} $O(n^2)$ {\kaishu 表示每次分割时处理所有单元格所需的时间。}

空间复杂度为：
\[
S(n) = O(n^2)
\]
递归栈空间为 $O(\log n)$，远小于主空间。

\textbf{结论}：分治递归迷宫生成算法能够保证生成的迷宫具有唯一通路且无孤立区域，且时间和空间复杂度均为 $O(n^2)$。

\subsubsection{\heiti 算法实现}
\noindent
\scalebox{1.10}{
    \begin{algorithm}[H]
    \footnotesize 
    \RaggedRight % 启用左对齐
    \caption{分治迷宫生成算法（递归部分）}
    \SetAlgoLined
    \DontPrintSemicolon
    \KwIn{子区域边界: (x1,y1,x2,y2)}
    \SetKwFunction{divConq}{divideAndConquerRecursive}
    \If{$(x2 - x1 < 4)$ \textbf{or} $(y2 - y1 < 4)$}{
        \Comment{小区域处理逻辑}
    \Return\; 
    }
    \Comment{初始化当前区域为路径}
    \For{$i \gets x1$ \KwTo $x2$}{
        \For{$j \gets y1$ \KwTo $y2$}{
            maze[i][j] $\gets$ PATH\;
        }
    }
$midX \gets (x1 + x2) / 2  \quad midY \gets (y1 + y2) / 2$ \;
    调整 $midX$, $midY$ 避开 rows/cols 中的门位置\;
    \Comment{构建十字分割墙}
    \For{$i \gets x1$ \KwTo $x2$}{
        maze[i][midY] $\gets$ WALL \Comment*{垂直墙}
    }
    \For{$j \gets y1$ \KwTo $y2$}{
        maze[midX][j] $\gets$ WALL \Comment*{水平墙}
    }
    \Comment{在十字墙上创建四个门,并随机关闭一个门}
    Up $\gets (x1 + midX)/2$;maze[Up][midY] $\gets$ PATH

    Down $\gets (midX + x2) / 2$;maze[Down][midY] $\gets$ PATH 

    Left $\gets (y1 + midY) / 2$; maze[midX][Left] $\gets$ PATH 

    Right $\gets (midY + y2) / 2$; maze[midX][Right] $\gets$ PATH 

    $closeIndex \gets$ random(0,3)\;
    根据 $closeIndex$ 关闭相应门（改为WALL）\; 
    \Comment{若是最外层区域，设置起点终点}
    \If{是迷宫最外层区域}{
        根据关闭的门位置设定 startPos 和 endPos\;
    }
    \Comment{递归处理四个子区域}
    \divConq(x1, y1, midX-1, midY-1)\; 
    \divConq(x1, midY+1, midX-1, y2)\; 
    \divConq(midX+1, y1, x2, midY-1)\; 
    \divConq(midX+1, midY+1, x2, y2)\; 
    \end{algorithm}
}

\subsection{\heiti 路径规划}
\subsubsection{\heiti 问题定义}
在一个迷宫中，规划一条从起点到终点的最优路径，使得在避开陷阱的同时，能够收集到尽可能多的资源。
首先，需要明确，在路径长度不做限制的情况下，最大化利益需要尽可能收集最多的资源，但不会为了收集资源而踩损失大于资源，从而导致入不敷出的陷阱与会导致损失的机关。
其次，由于存在死胡同的情况，需要存储路径信息与陷阱触发信息，从而进行有效的路径规划。
并且，从起点出发，最终来到终点，需要找到尽可能短的路径。
\subsubsection{\heiti 动态规划算法的最优子结构与重叠子问题性质证明}

\textbf{1. 最优子结构性质证明}

{\kaishu 定义：若一个问题的最优解可以由其子问题的最优解有效构造，则称该问题具有最优子结构性质。\cite{cormen2009introduction}}

{\kaishu 在本课设中的体现：}

设状态为 $(x, y, mask)$，表示当前在迷宫的 $(x, y)$ 位置，已收集资源的状态为 $mask$。记 $f(x, y, mask)$ 为从起点到 $(x, y)$ 并收集 $mask$ 状态下资源的最大净收益。

假设从起点到终点的最优路径为 $P$，其最后一步是从 $(x', y', mask')$ 转移到 $(x, y, mask)$。则有：
\[
\scalebox{0.9}{$f(x, y, mask) = \max \left\{ f(x', y', mask') + \text{收益/损失}(x, y) \right\}$}
\]
其中 $(x', y')$ 为 $(x, y)$ 的相邻格，$mask'$ 为未经过 $(x, y)$ 时的资源收集状态。

{\kaishu 证明：}

{\kaishu 若 $P$ 不是以最优方式到达 $(x', y', mask')$，则可以用更优的子路径替换 $P$ 的前半段，从而得到更优的整体路径，矛盾。因此，整体最优解必然由子问题的最优解递推得到，满足最优子结构性质。}

\vspace{2mm}
\textbf{2. 重叠子问题性质证明\cite{cormen2009intro}}

{\kaishu 定义：若一个问题在递归求解过程中会反复遇到相同的子问题，则称该问题具有重叠子问题性质。}

{\kaishu 在本课设中的体现：}

{\kaishu 在状态转移过程中，$f(x, y, mask)$ 的计算会多次遇到相同的 $(x, y, mask)$ 状态。例如，从不同路径到达同一格 $(x, y)$ 且资源收集状态相同（即 $mask$ 相同），其后续决策完全一致。因此，所有到达 $(x, y, mask)$ 的路径都可以合并为一个子问题，避免重复计算。}

{\kaishu 证明：}

{\kaishu 设有多条路径 $P_1, P_2, \ldots, P_k$ 到达同一状态 $(x, y, mask)$，则后续的最优策略与到达方式无关，只与当前状态有关。动态规划通过记忆化（或表格法）存储每个 $(x, y, mask)$ 的最优值，避免了对同一子问题的重复求解。这说明该问题具有重叠子问题性质。}

\vspace{2mm}
\textbf{3. 结论}

{\kaishu 综上，迷宫资源收集与路径优化问题的动态规划算法同时具备最优子结构和重叠子问题两大性质，适合采用动态规划方法高效求解。}

% \subsubsection{ 算法设计}
\subsubsection{\heiti 算法设计}

首先，针对迷宫资源收集与路径优化问题，本文设计并实现了一种三维状态压缩动态规划（DP）算法\cite{sedgewick2011algorithms}。该问题天然满足最优子结构和重叠子问题两大性质，适合采用动态规划方法进行高效求解。

在DP状态设计方面，考虑到迷宫本身为二维结构，但为了记录资源收集的情况以实现利益最大化，引入第三维以区分每一个点在不同资源收集状态下的最优解。具体地，DP状态可表示为
\[
dp[x][y][mask]
\]
其中 $(x, y)$ 表示当前位置，$mask$ 为二进制位掩码，记录已收集资源的状态。通过状态压缩，有效降低了空间复杂度。

算法流程采用广度优先搜索（BFS）结合优先队列进行状态扩展。每次从队列中取出当前状态，遍历四个方向的相邻位置，对于每一个新位置，计算因踩中陷阱带来的损失和收集资源带来的收益，更新资源收集位掩码，并将新状态加入队列。为保证算法效率，采用循环次数限制（如20000次）\cite{yan2013datastruct}进行剪枝，防止状态爆炸。

在实现过程中，利用 \texttt{map} 对资源和陷阱的位置进行编号，便于通过位置快速查询对应的资源或陷阱编号。每次状态转移时，通过三元组 $(x, y, mask)$ 进行判重和最优性判断，确保不会重复扩展无效状态。

本算法极大地优化了资源和陷阱的访问效率，显著提升了整体求解性能。时间复杂度方面，状态空间的压缩和高效判重机制有效控制了算法的运行时间和内存消耗，适合大规模迷宫场景下的最优路径与资源收集问题。

\subsubsection{\heiti 动态规划状态转移方程及复杂度分析}

\textbf{1. 状态转移方程}

设 $dp[x][y][mask]$ 表示从起点出发，到达迷宫位置 $(x, y)$，并且已收集资源状态为 $mask$ 时的最大净收益。则状态转移方程为：
\begin{align*}
dp[x][y][mask] & = \max\limits_{(x',y') \in \text{adj}(x,y)} \Big\{ \ 
  dp[x'][y'][mask'] \\
    & +\ \text{收益}(x, y) - \text{损失}(x, y) \Big\}
\end{align*}

其中：
$(x', y')$ 表示 $(x, y)$ 的相邻格子；
$mask'$ 表示未经过 $(x, y)$ 时的资源收集状态；
$\text{收益}(x, y)$ 表示当前位置收集到的资源价值（若有）；
$\text{损失}(x, y)$ 表示当前位置因陷阱等带来的损失（若有）。

每次状态转移时，若当前位置有新资源且未被收集，则更新 $mask$，否则 $mask$ 保持不变。

\textbf{2. 时间复杂度分析}

假设迷宫规模为 $n \times n$，资源总数为 $k$，则状态空间大小为 $O(n^2 \cdot 2^k)$。每个状态最多有 $4$ 个方向的转移。由于每次状态转移时需要通过 \texttt{map} 查找当前位置是否为陷阱或资源，其查找复杂度为 $O(\log k)$，因此总的时间复杂度为：
\[
T(n) = O(n^2 \cdot 2^k \cdot \log k)
\]
{\kaishu 其中，$n$ 表示迷宫的边长，$k$ 表示资源或陷阱的总数。空间复杂度同样为 $O(n^2 \cdot 2^k)$。}

\textbf{3. 空间复杂度分析}

需要存储所有 $dp[x][y][mask]$ 状态，空间复杂度为：
\[
 T(n) = O(n^2 \cdot 2^k)
\]

{\kaishu 其中，$n$ 表示迷宫的边长，$k$ 表示资源的总数。由于状态压缩，算法在保证精确性的同时大幅降低了空间和时间消耗，适合中等规模迷宫的最优路径与资源收集问题。}
\subsubsection{\heiti 算法实现}

\noindent
\scalebox{1.2}{%
\begin{algorithm}[H]
\footnotesize
\SetAlgoSkip{smallskip}
\DontPrintSemicolon
\caption{三维状态压缩动态规划算法}
\label{alg:dp}
\LinesNumbered
\KwIn{迷宫矩阵 $maze$，资源集合 $R$，陷阱集合 $T$，\\ 起点 $(sx, sy)$，终点 $(ex, ey)$}
\KwOut{最大净收益 $maxProfit$ 及其路径 $bestPath$}
\LinesNumbered
初始化三维DP数组 $dp[x][y][mask] \leftarrow -\infty$\;
初始化前驱数组 $pre[x][y][mask]$\;
初始化队列 $Q$ \quad  $dp[sx][sy][0] \leftarrow 0$\;
将 $(sx, sy, 0)$ 加入队列 $Q$\;

\While{队列 $Q$ 非空}{
    从队列 $Q$ 中取出 $(x, y, mask)$\;
    \For{每个方向 $(dx, dy) \in \{(0,1), (0,-1), (1,0), (-1,0)\}$}{
        $nx \leftarrow x + dx$ \,\, $ny \leftarrow y + dy$\;
        \If{$maze[nx][ny]$ 可通行}{
            $newMask \leftarrow mask$\;
            $profit \leftarrow dp[x][y][mask]$\;
            
            \If{$(nx, ny) \in R$ 且该资源未被收集}{
                获取资源编号 $idx$\;
                $newMask \leftarrow mask \mid (1 << idx)$\;
                $profit \leftarrow profit +$ 资源价值
                % $(nx, ny)$\;
            }
            
            \If{$(nx, ny) \in T$ 且首次触发}{
                $profit \leftarrow profit -$ 陷阱损失
                % $(nx, ny)$\;
            }
            
            \If{$profit > dp[nx][ny][newMask]$}{
                $dp[nx][ny][newMask] \leftarrow profit$\;
                $pre[nx][ny][newMask] \leftarrow (x, y, mask)$\;
                将 $(nx, ny, newMask)$ 加入队列 $Q$\;
            }
        }
    }
}

$maxProfit \leftarrow \max\limits_{mask} dp[ex][ey][mask]$\;
$bestMask \leftarrow \arg\max\limits_{mask} dp[ex][ey][mask]$\;
通过 $pre$ 数组回溯得到最优路径 $bestPath$\;
\Return{$maxProfit, bestPath$}\;
\end{algorithm}
}
\subsubsection{\heiti 结果展示}

% \begin{figure}[H]
%   \centering
%   \includegraphics[height = 7cm]{image/result1.png}
%   \caption{动态规划算法求解的最优路径示例}
%   \label{fig:example}
% \end{figure}
\begin{figure}[H]
  \centering
  \begin{adjustbox}{scale=0.3}
     \includegraphics{image/2-2-7.pdf}
  \end{adjustbox}
  \caption{动态规划算法求解的最优路径示例}
  \label{fig:example2}
\end{figure}
\subsection{\heiti 贪心算法}

\subsubsection{贪心选择性质与策略}

贪心算法适用于具有"贪心选择性质"的问题，即每一步都做出当前最优选择，期望最终获得全局最优解或近似最优解。\cite{skiena2008design}对于本课设的资源收集问题，虽然全局最优路径需动态规划求解，但在实际游戏中，玩家往往只能基于有限视野做出局部最优决策。此时，采用贪心策略能够在保证计算效率的同时获得较优的资源收益，尤其适合实时决策场景。

在本系统中，玩家以当前位置为中心，获取九宫格（$3\times3$）范围内的所有可达资源点。对于每个资源点，计算其性价比（优先级）：
\[
\text{Priority}(r) = \frac{\text{Value}(r)}{\text{Dist}(r)}
\]
其中，$\text{Value}(r)$ 表示资源点 $r$ 的价值，$\text{Dist}(r)$ 表示当前位置到 $r$ 的最短路径长度（可用BFS计算）。每次选择性价比最高的资源点作为下一个目标，沿最短路径前进并收集资源。

\subsubsection{贪心及通路获取策略}

贪心算法不仅仅局限于单步的局部最优选择，还结合了动态视野更新与全局路径调整机制\cite{bentley2000pearls}。具体而言，玩家每次到达目标资源点后，会重新获取当前位置的九宫格视野，评估当前可达资源的性价比，并再次执行贪心选择。该过程不断迭代，直至视野范围内已无可收集资源。

当九宫格视野内不存在可达资源时，系统自动切换为全局路径搜索，采用广度优先搜索（BFS）算法计算当前位置到终点的最短通路。玩家沿该通路前进，在前进过程中，若九宫格视野内再次出现新的可达资源，则中断探索当前通路，重新进入贪心选择流程。如此循环，直至玩家顺利到达终点。

注：在贪心自动寻路过程中，我们考虑了攻打BOSS和解密的情况，因此在到达终点时，可能会有BOSS战斗或解密关卡。如果遇到这种情况，我们会发送信号，暂时停止自动寻路，而当战斗或解密结束后，关闭对应窗口时，会有自定义的信号发送，通知贪心算法继续进行自动寻路。

该策略兼顾了局部最优与全局调整的灵活性，能够在保证资源收集效率的同时，动态应对迷宫环境的变化。通过在通路行进过程中不断检测视野内资源，系统能够及时捕捉新的收集机会，进一步提升整体收益。

{\kaishu 综上，贪心及通路获取策略通过"局部贪心—全局BFS—动态回溯"三者的有机结合，实现了高效且智能的资源收集路径规划，兼具实时性与适应性。}

\subsubsection{时间与空间复杂度分析}

% 每一步最多遍历九宫格内的 $O(1)$ 个格子，计算每个资源点的最短路径可用BFS，复杂度为 $O(n^2)$。假设总资源数为 $k$，则总时间复杂度为 $O(k n^2)$。若在无资源时调用一次全局BFS到终点，最坏情况下总复杂度为 $O(k n^2 + n^2)$，即 $O(k n^2)$。
每一步最多遍历九宫格内的 $O(1)$ 个格子，计算每个资源点的最短路径可用BFS，复杂度为 $O(n^2)$。假设总资源数为 $k$，在最坏的情况下，我们每到一个资源处，紧接着周围又变为没有资源的情况，且假设最终路径长度接近$n^2$，而没走一步，我们探索视野所需的时间复杂度为$O(8n)$最坏情况下总复杂度为 $O(k n^2 + 8 n^2)$，即 $O(n^2)$。

空间复杂度主要为BFS队列和路径记录，均为 $O(n^2)$。

{\kaishu 因此，贪心算法通过局部最优选择和动态调整，实现了高效的资源收集，适合实时决策场景，且时间和空间复杂度均优于全局动态规划。}

\subsubsection{贪心资源收集与通路获取算法伪代码}  
    \noindent
\scalebox{1.1}{
\begin{algorithm}[H]
\footnotesize
\caption{九宫格视野下的贪心资源收集}
\KwIn{迷宫矩阵 $maze$，资源集合 $R$，\\起点 $(sx, sy)$，终点 $(ex, ey)$}
\KwOut{资源收集路径 $greedyPath$}
当前位置 $cur \gets (sx, sy)$\;
初始化 $greedyPath \gets [cur]$\;
\While{未到达终点}{
    获取 $cur$ 九宫格范围内所有可达资源点 $S$\;
    \If{$S$ 非空}{
        \For{每个 $r \in S$}{
            计算 $\text{Priority}(r) = \frac{\text{Value}(r)}{\text{Dist}(r)}$\;
        }
        选择 $r^* = \arg\max\limits_{r \in S} \text{Priority}(r)$\;
        沿最短路径移动到 $r^*$，收集资源，\\
        更新 $cur$,将路径加入 $greedyPath$\;
    }
    \Else{
        计算 $cur$ 到 $(ex, ey)$ 的最短路径 $P_{end}$\;
        \For{沿 $P_{end}$ 的每一步}{
            $cur \gets$ 下一步位置\;
            将 $cur$ 加入 $greedyPath$\;
            获取 $cur$ 九宫格范围内所有资源点 $S$\;
            \If{$S$ 非空}{
                \textbf{break}，重新进入贪心选择流程\;
            }
        }
        \If{已到达终点}{
            \textbf{break}\;
        }
    }
}
\Return{$greedyPath$}\;
\end{algorithm}
}
\subsubsection{结果展示}

% \begin{figure}[H]
%   \centering
%   \includegraphics[height = 6cm]{image/result2.png}
%   \caption{贪心算法求解的资源收集路径示例}
%   \label{fig:example2}
% \end{figure}
\begin{figure}[H]
  \centering
  \begin{adjustbox}{scale=0.28}
     \includegraphics{image/2-2-8.pdf}
  \end{adjustbox}
  \caption{贪心算法求解的资源收集路径示例}
  \label{fig:example2}
\end{figure}
\subsection{\heiti BOSS战与分支限界法分析}

\subsubsection{分支限界法的设计思想}

在BOSS战回合优化问题中，目标是在有限回合内通过合理的技能释放顺序，最小化击败所有BOSS所需的回合数。由于技能存在冷却时间和伤害差异，状态空间极大，直接枚举所有可能序列不可行。为此，本文采用分支限界法（Branch and Bound），结合逆向思维对伤害上界进行估计，实现高效剪枝，显著优化搜索时间复杂度。

\subsubsection{逆向思维与伤害上界估计}

逆向思维指的是在每个状态节点，预估当前剩余BOSS血量在最优技能释放下所需的最小回合数，作为该节点的回合数的下界。若该下界已不优于当前已知最优解，则直接剪枝，无需扩展该分支。具体地，假设Boss个数为$m$，当前剩余血量为 $H$，假设我们的技能重新冷却且相互之间的冷却没有冲突，以此计算每个技能在$n$回合内的最大使用次数，来计算$n$回合内容能打出的最大伤害 $D_{max}^{n}$，则理论最少回合数为：
\[
% \text{LowerBound} = \left\lceil \frac{H}{D_{max}} \right\rceil
\text{LowerBound} = \{ n \mid  D_{max}^{n-1} < H \leq D_{max}^{n} \} + m;
\]
该下界用于剪枝判定。

\subsubsection{剪枝函数}

设当前已用回合数为 $t$，估计剩余回合下界为 $h(n)$，当前全局最优解为 $T_{best}$，则剪枝条件为：
\[
t + h(n) \geq T_{best}
\]
若满足该条件，则当前分支不可能产生更优解，直接剪枝\cite{kleinberg2005design}。

\subsubsection{时间与空间复杂度分析}

分支限界法通过下界估计和有效剪枝，大幅减少了实际搜索空间。设技能数为 $k$，Boss个数为$m$,Boss剩余血量为$H$,最终技能序列为 $T$，最大回合数为$n$,则计算伤害上界的时间复杂度为 $O(nk + klogk)$，最坏理论最坏情况下状态空间为 $O(k^T)$，但实际由于大量剪枝，搜索树规模远小于全排列。每个节点的下界估计和剪枝判定均为 $O(logH)$，总的时间复杂度为 $O(k^T)$。

空间复杂度主要为优先队列，最坏为 $O(k^T)$，实际远小于状态总数。

{\kaishu 综上，分支限界法结合逆向伤害上界估计与高效剪枝策略，实现了BOSS战最优技能序列的高效搜索，兼顾解的最优性与算法的可扩展性。}

\subsubsection{\heiti 分支限界法伪代码}

% \scalebox{0.75}{%
% \begin{algorithm}[H]
% \caption{分支限界法求解最小回合序列}
% \SetAlgoLined
% \LinesNumbered
% \KwIn{
%     $\text{BossHP}$: Boss的血量向量 \\
%     $\text{skills}$: 可用技能列表 \\
%     $\text{limitTurns}$: 回合数上限
% }
% \KwOut{最小回合数对应的技能序列}

% \SetKwFunction{initArr}{initArr}
% \SetKwFunction{estimate}{RemainTurns}
% \SetKwFunction{usedCool}{usedIndexCooldown}
% \SetKwFunction{updateCool}{updateCooldown}

% 初始化优先队列 $pq$ (按 $Fn$ 值排序的最小堆)\;
% \initArr{$limitTurns, skills$}\;
% 创建初始节点 $initial$\;

% $pq.\text{push}(initial)$\;

% $minTurns \gets \text{limitTurns}$\;
% $bestSequence \gets \emptyset$\;

% \While{$!pq.\text{empty}()$}{
%     $current \gets pq.\text{top}()$\; 
%     $pq.\text{pop}()$\;
    
%     \If{$current.Fn \geq minTurns$}{
%         \textbf{continue}\;
%     }
    
%     \uIf{$current.\text{currentBoss} \geq \text{BossHP.size}()$}{
%         \If{$current.\text{turns} < minTurns$}{
%             $minTurns \gets current.\text{turns}$\;
%             $bestSequence \gets current.\text{skillSequence}$\;
%         }
%         \textbf{continue}\;
%     }
    
%     \For{\textbf{each skill} $i$ \textbf{in} $\text{skills}$}{
%         \If{$current.\text{cooldowns}[i] = 0$}{
%             $next \gets current$\;
%             $next.\text{bossHP}[\text{currentBoss}] \gets next.\text{bossHP}[\text{currentBoss}] - \text{skills}[i].\text{getDamage}()$\;
%             $next.\text{turns} \gets next.\text{turns} + 1$\;
            
%             \If{$next.\text{bossHP}[current.\text{currentBoss}] \leq 0$}{
%                 $next.\text{currentBoss} \gets next.\text{currentBoss} + 1$\;
%             }
%             \usedCool{$next.\text{cooldowns}, \text{skills}, i$}\;
%             \updateCool{$next.\text{cooldowns}, \text{skills}$}\;

%             $next.Fn \gets next.\text{turns} + \estimate{next, skills, limitTurns}$\;
            
%             $next.\text{skillSequence}.\text{pushBack}(i)$\;
%             $pq.\text{push}(next)$\;
%         }
%     }
% }
% \Return{$bestSequence$}\;
% \end{algorithm}
% }% end of scalebox
\noindent
\scalebox{1.08}{
    \footnotesize
    \begin{algorithm}[H]
    \caption{分支限界法求解最小回合序列}
    \SetAlgoLined
    \KwIn{
        $\text{BossHP}$: Boss的血量向量 \\
        $\text{skills}$: 可用技能列表 \,\,
        $\text{limitTurns}$: 回合数上限
    }
    \KwOut{最小回合数对应的技能序列}

    \SetKwFunction{initArr}{initArr}
    \SetKwFunction{estimate}{RemainTurns}
    \SetKwFunction{usedCool}{used\_index\_cooldown}
    \SetKwFunction{updateCool}{update\_cooldown}

    初始化优先队列 $pq$ (按 $Fn$ 值排序的最小堆)\;
    \initArr{$limitTurns, skills$} \Comment*{计算伤害上界}
    创建初始节点 $initial$  \quad $pq.\text{push}(initial)$\;

    $minTurns \gets \text{limitTurns}$ \Comment*{初始化最小回合数}
    $bestSequence \gets \emptyset$ \Comment*{最佳技能序列}

    \While{$!pq.empty()$}{
        $current \gets pq.\text{top}()$ \\ $pq.\text{pop}()$\;
        
        \If{$current.Fn \geq minTurns$}{
            \textbf{continue} \Comment*{界限剪枝：无法优化当前最优解}
        }
        
        \uIf{$current.\text{currentBoss} \geq \text{BossHP.size()}$}{
            \If{$current.\text{turns} < minTurns$}{
                $minTurns \gets current.\text{turns}$\;
                $bestSequence \gets current.\text{skillSequence}$\;
            }
            \textbf{continue}\;
        }
        
        \For{\textbf{each skill} $i$ \textbf{in} $\text{skills}$}{
            \If{$current.\text{cooldowns}[i] = 0$}{
                $next \gets current$ \Comment*{创建子节点}
                $next.\text{bossHP}[cur] -= \text{skills}[i].\text{getDamage}()$\;
                $next.\text{turns} += 1 $\;
                
                \If{$next.\text{bossHP}[current.\text{currentBoss}] \leq 0$}{
                    $next.\text{currentBoss} += 1$
                }
                \usedCool{$next.\text{cooldowns}, \text{skills}, i$}\;

                \updateCool{$next.\text{cooldowns}, \text{skills}$}\;

                $next.Fn = next.\text{turns} + \estimate{$next, skills, limitTurns$}$\;
                
                $next.\text{skillSequence}.\text{push\_back}(i)$ \Comment*{记录}
                $pq.\text{push}(next)$\;
            }
        }
    }
    \Return{$bestSequence$}\;
    \end{algorithm}
}
\subsubsection{\heiti 结果展示}

% \begin{figure}[H]
%   \centering
%   \includegraphics[height = 6cm]{image/result3.png}
%   \caption{分支限界法求解的BOSS战示例}
%   \label{fig:example3}
% \end{figure}
\begin{figure}[H]
  \centering
  \begin{adjustbox}{scale=0.3}
     \includegraphics{image/2-2-9.pdf}
  \end{adjustbox}
  \caption{分支限界法求解的BOSS战示例}
  \label{fig:example3}
\end{figure}

\subsubsection{\heiti 问题分析}

回溯法（Backtracking）适用于解空间呈树状结构\cite{weiss2006datastruct}、需要枚举所有可行解并通过条件筛选得到目标解或者找出所有满足要求的可行解的问题。在本课设的解谜模块中，解决的问题是三位密码锁的破解：题目给我们提供了一些线索，对密码有了一些特别的限制，如有特定取值范围和约束（如素数、不重复、奇偶性等），目标是枚举所有可能的排列组合，找出正确的密码。

\subsubsection{\heiti 算法设计说明}

我们的回溯法采用递归方式逐步构造解的每一部分。在每一层递归中，尝试每位密码所有可能的选择，并在每次选择后判断当前部分解是否满足约束条件（即剪枝）。若满足，则递归进入下一层；若不满足，则立即回溯，避免无效搜索。最终在递归终点判断整体解的合法性，若合法则记录或输出。

\subsubsection{\heiti 剪枝函数与judge函数分析}

在回溯法的实现过程中，\texttt{judge} 函数是剪枝操作的核心。该函数用于判断当前部分解是否满足所有已知约束条件，从而决定是否继续递归扩展或立即回溯。其本质是将全局约束条件局部化到每一步递归中，提前排除不可能得到合法解的分支，极大提升搜索效率。

以三位密码锁问题为例，\texttt{judge} 函数常见的判定逻辑包括：
\begin{itemize}
    \item 检查当前数值是否为指定数值b；
    \item 检查当前数字是否满足素数、且不重复；
    \item 检查当前数字是否满足奇数或偶数的要求。
\end{itemize}

\texttt{judge} 函数的设计应尽可能高效，优先判断最容易被否定的条件，以便及早剪枝，减少递归深度和无效搜索。合理的 \texttt{judge} 实现是回溯法高效性的关键。

\subsubsection{\heiti 时间与空间复杂度分析}

假设第i位密码有 $d_{i}$ 种可能取值，密码长度为 $n$，则无剪枝时总状态数为 $O(\prod_{i=1}^{n} d_i)$。剪枝函数有效时，可大幅减少实际搜索空间。每次递归调用的空间复杂度为 $O(n)$（递归栈深度），整体空间复杂度为 $O(n)$。

{\kaishu 综上，回溯法通过递归枚举和高效剪枝，能够在保证解的完整性的同时，显著降低无效搜索，适合解空间有限、约束明确的组合优化问题。其中，\texttt{judge} 函数通过对部分解的实时约束判定，实现了回溯法的高效剪枝，是保证算法性能和正确性的核心组件。}

\subsection{\heiti 结果展示}

\begin{figure}[H]
  \centering
  \begin{adjustbox}{scale=0.28}
     \includegraphics{image/2-2-10.pdf}
  \end{adjustbox}
  \caption{回溯法求解的密码锁示例}
  \label{fig:example4}
\end{figure}

\subsection{\heiti 回溯法伪代码}
\noindent
\scalebox{1.25}{%
    \footnotesize
\begin{algorithm}[H]
\caption{回溯法求解数字排列问题}
\SetAlgoLined
\KwIn{当前递归层数 $n$}
\KwOut{布尔值表示是否找到解 \\引用参数 $cnt$ 记录尝试次数}
\SetKwFunction{backtrack}{Backtracking}

\If{$n == 3$} { 
    \tcp{达到递归终点（第3层）}
    $str \gets \text{genHashCode}(arr[1], arr[2], arr[3])$ \tcp*{哈希}
    \If{$\text{isCorrect}(str)$} {
        \tcp{验证是否满足条件}
        $\text{setValue}(arr[1] \times 100 + arr[2] \times 10 + arr[3])$ 
        \Return{\bf true}\;
    }
    \Else{
        $cnt \gets cnt + 1$ \tcp*{增加尝试计数器}
        \Return{\bf false}
    }
}
\Else{ 
    \tcp{递归分支处理}
    $t \gets arr[n+1]$ \tcp*{保存当前状态}
    \For{$i \gets arr[n+1]$ \KwTo $9$}{ 
        $arr[n+1] \gets i$ \tcp*{设置新值}
        \tcp{检查新值是否合法}
        \If{$\text{judgeI}(n+1)$}{ 
            \tcp{满足条件则递归进入下一层}
            % \Comment*{递归进入下一层}
            \If{$\backtrack(n+1, cnt)$}{ 
                \Return{\bf true}
            }
        }
    }
    $arr[n+1] \gets t$ \tcp*{恢复原始状态}
    \Return{\bf false} \tcp*{当前分支无解}
}
\end{algorithm}
}

% \subsection{\heiti 对投稿的基本要求}

% (1) 研究性论文主体应包括引言(重点论述研究的科学问题、意义、解决思路、价值、贡献等)、相关工作(为与引言部分独立的一个章节)、主要成果论述、关键实现技术、验证(对比实验或理论证明)、结论(结束语)等内容；系统实现或实验应有关键点的详细论述，以便读者能够重复实现论文所述成果。实验应有具体的实验环境设置、全面细致的数据对比分析。

% (2) 综述应包括引言、问题与挑战、研究现状分析、未来研究方向、结论等内容。以分析、对比为主，避免堆砌文献或一般性介绍、叙述。

% (3) 定理证明、公式推导、大篇幅的数学论述、原始数据，放到论文最后的附录中。

% {\bf 稿件提交时的基本要求：}

% (1) 本模板中要求的各项内容正确齐全，无遗漏；
% (2) 语句通顺，无中文、英文语法错误，易于阅读理解，符号使用正确，图、表清晰无误；

% (3) 在学术、技术上，论文内容正确无误，各项内容确定。

% {\heiti \subsection{二级标题 *字体为5号黑体*标题2}}
% \subsubsection{三级标题 *字体为5号宋体*标题3}
% *正文部分, 字体为5号宋体* 正文文字

% \textbf{正文文字要求语句通顺，无语法错误，结构合理，条理清楚，不影响审稿人、读者阅读理解全文内容。以下几类问题请作者们特别注意}：

% 1) 文章题目应明确反映文章的思想和方法；文字流畅，表述清楚；

% 2) 中文文字、英文表达无语法错误；

% 3) 公式中无符号、表达式的疏漏，没有同一个符号表示两种意思的情况；

% 4) 数学中使用的符号、函数名用斜体；

% 5) 使用的量符合法定计量单位标准；

% 6) 矢量为黑体，标量为白体；

% 7) 变量或表示变化的量用斜体；

% 8) 图表规范，量、线、序无误，位置正确(图表必须在正文中有所表述后出现，即{\ldots}如图1所示)(注意纵、横坐标应有坐标名称和刻度值)。

% 9) 列出的参考文献必须在文中按顺序引用，即参考文献顺序与引用顺序一致，各项信息齐全(格式见参考文献部分)；

% 10) 首次出现的缩写需写明全称，首次出现的符号需作出解释。

% 11) 图的图例说明、坐标说明全部用中文或量符号。

% \textbf{12) 图应为矢量图。}

% 13) 表中表头文字采用中文。

% 14) 公式尺寸：

% 标准：10.5磅

% 下标/上标：5.8磅

% 次下标/上标：4.5磅

% 符号：16磅

% 次符号：10.5磅

% 15) 组合单位采用标准格式，如：``pJ/bit/m$^{4}$''应为 ``pJ/(bit$\cdot
% $m$^{4})$''

% \textbf{定理1}.\quad ******. *定理内容.*

% [``定义''、``假设''、``公理''、``引理''等的排版格式与此相同，详细定理证明、公式可放在附录中]

% \texttt{证明}.\quad  *证明过程.* [``例 x''等的排版格式相同]

% \rightline {证毕.}

% \begin{figure}[H]
% \centerline{\fbox{\rule{0pt}{1.98in}\rule{3.15in}{0pt}}}
% {\zihao{5}图X\quad  图片说明 *占位图*}
% \label{fig1}
% \end{figure}

% \begin{table}[H]
% \centering {\heiti 表X\quad 表说明 *表说明采用黑体*}
% % \caption{表说明 *表说明采用黑体*}
% \vspace {-2.5mm}
% \begin{center}
% \begin{tabular}{ll}
% \toprule
% *示例表格*&*第1行为表头,表头要有内容* \\
% \hline
% &
%  \\
% &
%  \\
% &
%  \\
% &
%  \\
% \bottomrule
% \end{tabular}
% \label{tab1}
% \end{center}
% \end{table}

% {\heiti 过程X}.\quad 过程名称

% {\zihao{5-}*《计算机学报》的方法过程描述字体为小5号宋体，IF、THEN等伪代码关键词全部用大写字母，变量和函数名称用斜体*}


% {\heiti 算法\textbf{Y}}.\quad 算法名称.
% {\zihao{5-}

% \noindent 输入：{\ldots} {\ldots}

% \noindent 输出：{\ldots} {\ldots}

% *《计算机学报》的算法描述字体为小5号宋体, IF、THEN等伪代码关键词全部用大写字母，变量和函数名称用斜体*}

% \subsubsection{参考文献}
% 这是参考文献示例。参考文献应遵循GB/T 7741-2015标准。引用文献1~\cite{Bohan1928}，文献2~\cite{chen1980zhongguo}，文献3-5~\cite{bravo1990comparative,niu2013zonghe,yuan2012lana}。

\vspace {3mm}
\zihao{5}{
\noindent \textsf{致\quad 谢}\quad \textit{ 一个好的程序离不开良好的团队协作，尽管时间紧迫，任务繁重，但大家齐心协力，克服了一个又一个困难，最终顺利完成了项目。当然我们的项目仍有许多不足之处需要改进，但整体上不失一个良好的项目，再次非常感谢大家的努力与付出！此外，感谢老师与助教学姐的指导与帮助，让我们从这个项目中收获了很多知识和技能。愿大家继续 Stay hungry. Stay foolish. }}

\vspace {5mm}
\centerline
{\zihao{5}\textsf{参~考~文~献}}
\zihao{5-} \addtolength{\itemsep}{-1em}
\vspace {1.5mm}
\bibliographystyle{gbt7714-numerical}
\bibliography{ref.bib}

\end{multicols}

% \begin{multicols}{1}
% \noindent {\zihao{5}\bf{附录X}.}

% {\zihao{5-}\setlength\parindent{2em}
% *\textbf{附录内容}置于此处，字体为小5号宋体。附录内容包括：\textbf{详细的定理证明、公式推导、原始数据}等*}\\\\

% \end{multicols}


\begin{multicols}{1}
\begin{biography}[image/signature1.jpg]
\noindent
\textbf{王稳淞  \quad 工作量：30\%}\ \ 

负责任务一和任务二，分治法生成地图和动态规划生成最优路径。主笔编写课程设计报告。参与制作PPT和汇报。突出贡献为分治法生成地图的设计，三位状态压缩dp和报告编写
% *计算机学报第1作者提供照片电子图片，尺寸为1寸。英文作者介绍内容包括：出生年,学位(或目前学历),职称,主要研究领域(\textbf{与中文作者介绍中的研究方向一致}).*
% *字体为小5号Times New Roman*
\end{biography}

\begin{biography}[image/signature2.png]
\noindent
\textbf{程宇山  \quad 工作量：30\%}\ \ 

主要负责实现任务四，负责整个程序的界面设计。
具体实现地图动态生成、老虎机式解密设置、
boss战斗界面、贪心3*3视野与小地图路径显示。
% *英文作者介绍内容包括：出生年,学位(或目前学历),职称,主要研究领域(\textbf{与中文作者介绍中的研究方向一致})。*
% *字体为小5号Times New Roman*
\end{biography}
\end{multicols}

\begin{multicols}{1}
\begin{biography}[image/signature3.png]
\noindent
\textbf{徐伟杰 \quad 工作量：20\%}\ \ 

% *计算机学报第1作者提供照片电子图片，尺寸为1寸。英文作者介绍内容包括：出生年,学位(或目前学历),职称,主要研究领域(\textbf{与中文作者介绍中的研究方向一致}).*
% *字体为小5号Times New Roman*
主要负责任务三和ppt汇报，贪心选择算法以及自动寻路功能的实现，主要负责后端构建迷宫的基础类，不同模块间的相互嵌套调用，资源获取公式的构建以及寻路算法的实现；制作和主讲ppt并进行成员任务汇报流程的分配。
\end{biography}

\begin{biography}[image/signature4.png]
\noindent
\textbf{林书豪  \quad 工作量：20\%}\ \  

% *英文作者介绍内容包括：出生年,学位(或目前学历),职称,主要研究领域(\textbf{与中文作者介绍中的研究方向一致})。*
负责实现任务五。具体实现分支限界的算法，采用stl库的优先队列加剪枝，设计剪枝函数，参与设计降低该算法复杂度，在启发式搜索中将预估剩余回合数部分利用贪心的思想前置计算。
\end{biography}
\end{multicols}

% \begin{multicols}{1}
% \zihao{5}
% \noindent \textbf{Background}

% \zihao{5-}{
% \setlength\parindent{2em}
% *论文背景介绍为\textbf{英文}，字体为小5号Times New Roman体*

% 论文后面为400单词左右的英文背景介绍。介绍的内容包括：

% 本文研究的问题属于哪一个领域的什么问题。该类问题目前国际上解决到什么程度。

% 本文将问题解决到什么程度。

% 课题所属的项目。

% 项目的意义。

% 本研究群体以往在这个方向上的研究成果。

% 本文的成果是解决大课题中的哪一部分，如果涉及863$\backslash
% $973以及其项目、基金、研究计划，注意这些项目的英文名称应书写正确。}

% \end{multicols}
\end{document}
